﻿// ex5.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include "pch.h"
#include <iostream>
# include<stdio.h>
#define MAX_SIZE 100

typedef struct bitnode
{
	int data;
	bitnode *lch;
	bitnode *rch;
}*bitree;

int binary_search(int arr[], int key, int left, int right)
{
	while (left <= right)
	{
		int mid = left + ((right - left) / 2);
		if (key > arr[mid])
		{
			left = mid + 1;
		}
		else if (key < arr[mid])
		{
			right = mid - 1;
		}
		else
		{
			return mid;
		}
	}
	return -1;
}

int search(bitree T, int key, bitree f, bitree *p)
{
	if (!T) 
	{  
		*p = f;
		return 0;
	}
	else if (key == T->data)
	{

		*p = T;
		return 1;

	}
	else if (key < T->data) 
	{
		return search(T->lch, key, T, p);

	}
	else 
	{
		return search(T->rch, key, T, p);
	}
}

int insert(bitree *T, int key) 
{
	bitree p, s;

	if (!search(*T, key, NULL, &p)) {  // 没找到key

		s = (bitree)malloc(sizeof(bitnode));
		s->data = key;
		s->lch = s->rch = NULL;

		if (!p)
			*T = s;  // 插入 s 为新的根结点
		else if (key < p->data)
			p->lch = s;  //插入 s 为左孩子
		else
			p->rch = s; // 插入 s 为右孩子

		return 1;
	}
	else
		return 0;
}

void traverse(bitree T)
{
	if (!T)
		return;

	traverse(T->lch);
	printf("%d ", T->data);
	traverse(T->rch);
}
bitree findMin(bitree &root)
{
	if (root == NULL)
		return NULL;
	else if (root->lch == NULL)
		return root;
	return findMin(root->lch);     //递归查找 
}

//bitree findMax(bitree &root)
//{
//	if (root != NULL)                   //非递归查找 
//		while (root->rch != NULL)
//			root = root->rch;
//	return root;
//}

bitree delete_node(bitree &root, int data)
{
	if (root == NULL)
		return root;

	if (data < root->data)
		root->lch = delete_node(root->lch, data);
	else if (data > root->data)
		root->rch = delete_node(root->rch, data);
	else if (root->lch != NULL && root->rch != NULL)
	{
		root->data = findMin(root->rch)->data;
		root->rch = delete_node(root->rch, root->data);
	}
	else
		root = (root->lch != NULL) ? root->lch : root->rch;
	return root;
}




int main()
{
	printf("选择实验的功能：\n1.折半查找\n2.二叉排序树\n");
	printf("输入实验的功能：");
	int choice;
	scanf_s("%d",&choice);
	while (choice)
	{
		if (choice == 1)
		{
			int arr[MAX_SIZE];
			int size;
			int key;
			printf("请输入元素的个数：\n");
			scanf_s("%d", &size);
			printf("输入元素：");
			for (int i = 0; i < size; i++)
				scanf_s("%d", &arr[i]);
			int left, right;
			left = 0; right = size;
			printf("输入要查找的元素：");
			scanf_s("%d", &key);
			int ret = binary_search(arr, key, left, right);
			if (ret == -1)
			{
				printf("找不到\n");
			}
			else
			{
				printf("元素位置：%d\n", ret + 1);
			}
		}
		else if (choice == 2)
		{
			int i, s;
			int a[MAX_SIZE];
			printf("请输入元素的个数：\n");
			scanf_s("%d", &s);
			printf("输入元素：");
			for (int i = 0; i < s; i++)
				scanf_s("%d", &a[i]);
			//int a[10] = { 62,88,58,47,35,73,51,99,37,93 };

			bitree T = NULL;
			for (i = 0; i < s; i++) {  // 通过插入操作来构建二叉排序树
				insert(&T, a[i]);
			}

			printf("中序递归遍历二叉排序树：\n");
			traverse(T);
			printf("\n\n");

			printf("输入删除的元素");
			int j;
			scanf_s("%d", &j);
			delete_node(T, j);
			printf("删除结点后的结果为：\n");
			traverse(T);
			printf("\n\n");
		}
		else
		{
			printf("输入有误\n");
			return 0;
		}
		printf("输入实验的功能：");
		scanf_s("%d", &choice);
	}
	return 0;
}


// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门提示: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
